home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Magnum One
/
Magnum One (Mid-American Digital) (Disc Manufacturing).iso
/
d12
/
ddj0190.arc
/
STEVENS.LST
< prev
next >
Wrap
File List
|
1989-12-19
|
6KB
|
254 lines
_C PROGRAMMING COLUMN_
by Al Stevens
[LISTING ONE]
/* ----------- textsrch.h ---------- */
#define OK 0
#define ERROR !OK
#define MXTOKS 25 /* maximum number of tokens */
#define MAXFILES 512 /* maximum number of files */
#define MAPSIZE MAXFILES/16 /* number of ints/map */
/* ---- the search decision bitmap (one bit per file) ---- */
struct bitmap {
int map[MAPSIZE];
};
/* ------- the postfix expression structure -------- */
struct postfix {
char pfix; /* tokens in postfix notation */
char *pfixop; /* operand strings */
};
/* --------- the postfix stack ---------- */
extern struct postfix pftokens[];
extern int xp_offset;
/* --------- expression token values ---------- */
#define TERM 0
#define OPERAND 'O'
#define AND '&'
#define OR '|'
#define OPEN '('
#define CLOSE ')'
#define NOT '!'
#define QUOTE '"'
/* ---------- textsrch prototypes ---------- */
struct postfix *lexical_scan(char *expr);
struct bitmap exinterp(void);
void init_database(void);
struct bitmap search(char *word);
void process_result(struct bitmap);
[LISTING TWO]
/* ------------ exinterp.c --------------- */
/*
* An expression interpreter that processes the
* tokens on a postfix stack.
*/
#include "textsrch.h"
static struct postfix *pf = pftokens;
static struct bitmap pop(void);
static struct bitmap not(struct bitmap map1);
static struct bitmap and(struct bitmap map1, struct bitmap map2);
static struct bitmap or(struct bitmap map1, struct bitmap map2);
/* ----- entry to the interpreter
returns a bitmap which indicates the files
that match a search expression ------------- */
struct bitmap exinterp(void)
{
/* ------- find the top of the postfix stack ------- */
while (pf->pfix != TERM)
pf++;
/* ------- get the result of the expression ------- */
return pop();
}
/* ------ pops an operand and converts it to a bit map ------ */
static struct bitmap pop(void)
{
struct bitmap map1;
switch ((--pf)->pfix) {
case OPERAND:
map1 = search(pf->pfixop);
break;
case NOT:
map1 = not(pop());
break;
case AND:
map1 = and(pop(), pop());
break;
case OR:
map1 = or(pop(), pop());
break;
default:
break;
}
return map1;
}
/* ------- unary <not> operator ----------- */
static struct bitmap not(struct bitmap map1)
{
int i;
for (i = 0; i < MAPSIZE; i++)
map1.map[i] = ~map1.map[i];
return map1;
}
/* ------- binary <and> operator -------------- */
static struct bitmap and(struct bitmap map1, struct bitmap map2)
{
int i;
for (i = 0; i < MAPSIZE; i++)
map1.map[i] &= map2.map[i];
return map1;
}
/* ------- binary <or> operator -------------- */
static struct bitmap or(struct bitmap map1, struct bitmap map2)
{
int i;
for (i = 0; i < MAPSIZE; i++)
map1.map[i] |= map2.map[i];
return map1;
}
[LISTING THREE]
/* ---------- search.c ----------- */
/*
* stub functions to simulate the TEXTSRCH retrieval process
*/
#include <stdio.h>
#include <dir.h>
#include <string.h>
#include <process.h>
#include "textsrch.h"
static char names[MAXFILES][13];
static int namect;
static void setbit(struct bitmap *map1, int bit);
static int getbit(struct bitmap *map1, int bit);
/* --------- initialize the data base environment --------- */
void init_database(void)
{
struct ffblk ff;
int rtn;
rtn = findfirst("*.txt", &ff, 0);
while (rtn != -1 && namect < MAXFILES) {
strcpy(names[namect++], ff.ff_name);
rtn = findnext(&ff);
}
}
/* ------ search the data base for a match on a word ------ */
struct bitmap search(char *word)
{
int i;
FILE *fp;
char str[80];
struct bitmap map1;
for (i = 0; i < MAPSIZE; i++)
map1.map[i] = 0;
sprintf(str, "grep -l -i %s *.txt >hits", word);
system(str);
if ((fp = fopen("hits", "rt")) != NULL) {
while (fgets(str, 80, fp) != NULL) {
*strchr(str, ':') = '\0';
for (i = 0; i < MAXFILES; i ++) {
if (stricmp(str+5, names[i]) == 0) {
setbit(&map1, i);
break;
}
}
}
fclose(fp);
}
return map1;
}
/* ---- process the result of a query expression search ---- */
void process_result(struct bitmap map1)
{
int i;
for (i = 0; i < MAXFILES; i++)
if (getbit(&map1, i))
printf("\n%s", names[i]);
}
/* ------ sets a designated bit in the bit map ------ */
static void setbit(struct bitmap *map1, int bit)
{
int off = bit / 16;
int mask = 1 << (bit % 16);
map1->map[off] |= mask;
}
/* ------ tests a designated bit in the bit map ------ */
static int getbit(struct bitmap *map1, int bit)
{
int off = bit / 16;
int mask = 1 << (bit % 16);
return map1->map[off] & mask;
}
[LISTING FOUR]
/* ----------- textsrch.c ------------- */
/*
* The TEXTSRCH program.
*/
#include <stdio.h>
#include <process.h>
#include <string.h>
#include "textsrch.h"
void main(void)
{
char expr[80];
/* -------- initialize the text data base --------- */
init_database();
do {
/* ----- read the expression from the console ------ */
printf("\nEnter the search expression:\n");
gets(expr);
if (*expr) {
/* --- scan for errors and convert to postfix --- */
if (lexical_scan(expr) == NULL) {
/* ---- the expression is invalid ---- */
while(xp_offset--)
putchar(' ');
putchar('^');
printf("\nSyntax Error");
exit(1);
}
/* --- interpret the expression, search the data base,
and process the hits ------- */
process_result(exinterp());
}
} while (*expr);
}